﻿namespace _45跳跃游戏2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solution.Jump(new int[] { 2, 3, 1, 1, 4 }));
        }
    }
    public class Solution
    {
        public static int Jump(int[] nums)
        {
            int n = nums.Length;
            if (n <= 1)
                return 0;

            int maxPosition = nums[0];  // 当前能够跳到的最远位置
            int maxSteps = nums[0];     // 当前位置下一步能够跳的最远距离
            int jumps = 1;              // 跳跃次数

            for (int i = 1; i < n; i++)
            {
                if (maxSteps < i)
                {
                    jumps++;
                    maxSteps = maxPosition;
                }

                if (maxPosition < i + nums[i])
                    maxPosition = i + nums[i];
            }

            return jumps;
        }
    }
}